package main

import "fmt"

func setZeroes(matrix [][]int) {
	m := len(matrix)
	n := len(matrix[0])
	i0 := -1
	j0 := -1
out:
	for i := 0; i < m; i++ {
		for j := 0; j < n; j++ {
			if matrix[i][j] == 0 {
				i0 = i
				j0 = j
				break out
			}
		}
	}
	// no zero
	if i0 == -1 && j0 == -1 {
		return
	}
	// find all zeros
	for i := 0; i < m; i++ {
		if i == i0 {
			continue
		}
		for j := 0; j < n; j++ {
			if j == j0 {
				continue
			}
			if matrix[i][j] == 0 {
				matrix[i0][j] = 0
				matrix[i][j0] = 0
			}
		}
	}
	// clean
	for j := 0; j < n; j++ {
		if j == j0 {
			continue
		}
		flag := matrix[i0][j]
		if flag == 0 {
			// clean column j
			for i := 0; i < m; i++ {
				matrix[i][j] = 0
			}
		}
	}
	for i := 0; i < m; i++ {
		if i == i0 {
			continue
		}
		flag := matrix[i][j0]
		if flag == 0 {
			for j := 0; j < n; j++ {
				matrix[i][j] = 0
			}
		}
	}
	// clean first row and first column
	for j := 0; j < n; j++ {
		matrix[i0][j] = 0
	}
	for i := 0; i < m; i++ {
		matrix[i][j0] = 0
	}
}

func main() {
	//m := [][]int{
	//	{1, 1, 1},
	//	{1, 0, 1},
	//	{1, 1, 1},
	//}
	//setZeroes(m)
	//fmt.Printf("%#v\n", m)
	m := [][]int{
		{0, 1, 2, 0},
		{3, 4, 5, 2},
		{1, 3, 1, 5},
	}
	setZeroes(m)
	fmt.Printf("%#v\n", m)
}
